package jago02.jago0201.ag02_lineTable;

import java.util.Iterator;

/**
 * 链式表：单向链表
 * 杂化简：单向链表从首节点head开始一直往后追加节点元素，节点存储元素和下一个节点
 *
 * 解目录：
 *      1.用N表示单向链表长度，表示单向链表的元素个数
 *      2.内部类Node包含元素值和下个节点
 *      4.自然添加元素到单向链表就是新增数据节点，并追加到尾节点后（尾节点的next为空）
 *      5.单向链表指定位置添加元素就是循环指定位置index-1次拿到pre节点，然后新增新节点，pre的next指向新节点，新节点的next指向原来index节点，后N++
 *      6.移除单向链表指定位置元素就是循环指定位置index-1次拿到pre节点，然后将pre的next指向index节点的next节点，然后N--，并返回被删除元素
 *      7.查找元素在单向链表位置索引，未找到则返回-1
 * 复杂度：所有方法都是O(N)
 */
public class LineTable02_OneWayLinkList<T> implements Iterable<T> {
    //节点内部类
    private class Node{
        T item;
        Node next;
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    //头节点
    private Node head;
    //单向链表长度
    private int N;
    //构造
    public LineTable02_OneWayLinkList() {
        this.head = new Node(null,null);
        this.N = 0;
    }
    //置空单向链表
    public void clear(){
        this.N = 0;
    }
    //单向链表判空
    public boolean isEmpty(){
        return this.N == 0;
    }
    //获取单向链表长度
    public int length(){
        return this.N;
    }
    //向单向链表中插入元素
    public void insert(T t){
        //找到最末尾的节点
        Node node = this.head;
        while (node.next != null){
            node = node.next;
        }
        //创建新节点
        Node newNode = new Node(t,null);
        //将新节点放到末尾节点
        node.next = newNode;
        this.N++;
    }
    //向单向链表中指定位置插入元素
    public void insert(int index,T t){
        //找到index位置的前一个节点
        Node pre = this.head;
        //找到index位置的节点
        for (int i = 0; i < index-1; i++) {
            pre = pre.next;
        }
        //获取index位置的节点
        Node current = pre.next;
        //创建新节点,新节点的下个节点是current,并将新节点放到pre的next位置
        Node newNode = new Node(t,current);
        pre.next = newNode;
        this.N++;
    }

    //删除并返回单向链表指定索引元素
    public T remove(int index){
        //找到index位置的前一个节点
        Node pre = this.head;
        //找到index位置的节点
        for (int i = 0; i < index-1; i++) {
            pre = pre.next;
        }
        //获取index位置的节点
        Node current = pre.next;
        //前一个节点的next指向下一个节点
        pre.next = current.next;
        this.N--;
        return current.item;
    }

    //查找首次出现元素t的位置,找不到则返回-1
    public int indexOf(T t){
        Node node = this.head;
        for (int i = 0; node.next!=null; i++) {
            node = node.next;
            if (node.item.equals(t)){
                return i;
            }
        }
        return -1;
    }

    //反转单向链表
    public void reverse(){
        if (isEmpty()){
           return;
        }
        reverse(head.next);
    }
    //反转指定的结点curr,并把反转后的结点返回
    private Node reverse(Node curr) {
        //到链表尾部时，将头部设置成尾部，并返回
        if (curr.next == null){
            this.head.next = curr;
            return curr;
        }
        //递归反转当前节点的下一个节点，返回值就是反转后的链表,反转后的链表前后颠倒
        //后变前
        Node pre = reverse(curr.next);
        pre.next = curr;
        //将当前节点的下一个节点变为null
        curr.next = null;
        return curr;
    }


    private class OneWayLinkListIterator implements Iterator{
        private Node curr;

        public OneWayLinkListIterator() {
            this.curr = head;
        }

        @Override
        public boolean hasNext() {
            return this.curr.next != null;
        }
        @Override
        public Object next() {
            curr = curr.next;
            return curr.item;
        }
    }

    @Override
    public Iterator iterator() {
        return new OneWayLinkListIterator();
    }

    public static void main(String[] args) {
        LineTable02_OneWayLinkList<String> oneWayLinkList = new LineTable02_OneWayLinkList();
        oneWayLinkList.insert("张三");
        oneWayLinkList.insert("李四");
        oneWayLinkList.insert("王五");
        oneWayLinkList.insert(1,"老朱");
        System.out.println(oneWayLinkList);
        for (String str : oneWayLinkList) {
            System.out.print(str+" ");
        }
    }
}
